/*
 * File: ILS.c
 *
 * Integrantes:
 * @author	Jormar Arellano		(05-37840)	<jormar.arellano@gmail.com>
 * @author	Sabrina Fernández	(05-38163)	<sabrinamfm@gmail.com>
 */

#include "util.h"
#include "ILS.h"
#include "graph.h"
#include "LocalSearch.h"

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

void ils_defaults() {
    ils_iter = 10;
    ils_verbose = 0;
    ils_disturb = disturb_randomRecoloring;
    ils_acceptance = acceptance_thebest;
    ils_recoloring_k = 1;     // Numero de colores que recolorean
}

Graph *disturb_randomRecoloring(Graph* graph) {
    int i;
    int changeColor, newColor, totalColor;
    Vertex *v;
    ArrayList *vcolors;

    for(i=0; i<ils_recoloring_k; i++) {
        totalColor = getTotalColor(graph);

        // Elegimos el color a cambiar
        changeColor = rand()%totalColor + 1;

        // Ubicamos los vertices de ese color
        vcolors = graph->Vcolors->data[changeColor-1];

        while(vcolors->length) {
            v = vcolors->data[0];

            // Elegimos un color diferente
            do {
                newColor = rand()%totalColor + 1;
            } while (newColor == changeColor);

            setColor(graph, v, newColor);
        }

        // Asi que compactamos los conjuntos de colores
        removeDeadColors(graph);
    }

    return graph;
}

Graph *acceptance_thebest(Graph* g1, Graph *g2, int *count) {
    Graph *resp = g1;
    int color1 = getTotalColor(g1);
    int color2 = getTotalColor(g2);

    if(isFeasibleSolution(g2)) {
        if(color2<color1) {
            // Se encontro una mejor solucion.
            *count = 0;
            resp = g2;
        } else if(color1 == color2) {
            // Las dos soluciones son igual de buenas asi que se selecciona cualquiera.
            if(rand()%2 == 0) resp = g2;
        }
    }

    return resp;
}

Graph *ils(Graph *graph) {
    int i;
    int _aux_i=0;
    Graph *newSol, *aux;

    // No queremos que Localsearch imprima todo.
    ls_verbose--;

    initialSolution(graph);
    graph = apply_local_search(graph);

    // Estadisticas.
    long inicialColors = getTotalColor(graph);
    long inicialCost = penaltyCost(graph);
    int cambioSolucion = 0;
    int iTotal = 0;

    // Necesitamos otro grafo en memoria.
    newSol = cloneGraph(graph);

    for(i=0; i<ils_iter; i++) {
        // S' = S*
        colorMatch(newSol, graph);

        // Perturbamos la mejor solucion S' que tenemos
        ils_disturb(newSol);

        // Aplicamos busqueda local sobre S'
        newSol = apply_local_search(newSol);

        if(ils_acceptance(graph, newSol, &_aux_i) == newSol) {
            aux = graph;
            graph = newSol;
            newSol = aux;

            // VERBOSE
            if(ils_verbose) {
                if(i==0) {
                    printf("    + ILS: Encontre mejor solucion: %d colores\n", getTotalColor(graph));
                } else {
                    printf("    + ILS: Encontre una solucion igual de buena.\n");
                }
            }
            cambioSolucion++;
        }
        if(_steps) waitStep();
        iTotal++;
    }

    // Liberamos recursos
    freeGraph(newSol);

    // VERBOSE
    if(0<ils_verbose) {
        printf("Reporte de ILS:\n");
        printf("    >> Colores: %ld ==> %d\n", inicialColors, getTotalColor(graph));
        printf("    >> Costos: %ld ==> %ld\n", inicialCost, penaltyCost(graph));
        printf("    >> Veces que se cambio de solucion: %d\n", cambioSolucion);
        printf("    >> Iteraciones totales: %d\n", iTotal);
    }

    return graph;
}
